package leetcode_acm.stackAndQueue;

import org.junit.Test;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月22日 16:03
 */
public class MaxSlidingWindow {
    private class PQ{
        private final Deque<Integer> deque;
        public PQ(){
            deque = new LinkedList<>();
        }
        public void pop(int val){
            if(!deque.isEmpty() && val == deque.getFirst()){
                deque.removeFirst();
            }
        }
        public int getMaxVal(){
            if(deque.isEmpty()){
                return -1;
            }
            return deque.getFirst();
        }
        public void push(int val){
            while(!deque.isEmpty() && deque.getLast() < val){
                deque.removeLast();
            }
            deque.addLast(val);
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        PQ pq = new PQ();
        //维护滑动窗口
        int l = 0,r = k-1,n = nums.length;
        int len = nums.length-k+1,index = 0;
        int[] ans = new int[len];
        //1. 先初始化窗口
        for(int i = l;i <= r;i++){
            pq.push(nums[i]);
        }

        //2. 开始滑动窗口
        while(r+1< n){
            int leftNum = nums[l++];
            int rightNum = nums[++r];
            pq.push(rightNum);pq.pop(leftNum);
            ans[index++] = pq.getMaxVal();
        }
        return ans;
    }
    @Test
    public void test(){
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }
}
